﻿using System;
using System.Collections.Generic;

namespace System
{
	public class Delaunay
	{
		public List<DelaunayPoint> Points = new List<DelaunayPoint>();
		DelaunayTriangle FirstTriangle;
		public List<DelaunayTriangle> Triangles = new List<DelaunayTriangle>();

		public Delaunay()
		{
			Points.Clear();
			Triangles.Clear();
		}
		public Delaunay(V3D[] Pts)
			: this()
		{
			for (int i = 0; i < Pts.Length; i++)
				Points.Add(new DelaunayPoint(Pts[i]));
		}

		public DelaunayPoint AddPoint(V3D P)
		{
			DelaunayPoint Res = new DelaunayPoint(P);
			Points.Add(Res);
			if (Points.Count == 3)
				FirstTriangle = CreateTriangle(0, 1, 2);
			return Res;
		}
		public DelaunayTriangle CreateTriangle(params int[] idx)
		{
			return CreateTriangle(Points[idx[0]], Points[idx[1]], Points[idx[2]]);
		}
		public DelaunayTriangle CreateTriangle(params DelaunayPoint[] pts)
		{
			var X = Triangles.FindAll(x => Array.Exists(pts, y => y == x.P1) && Array.Exists(pts, y => y == x.P2) && Array.Exists(pts, y => y == x.P3));
			if (X.Count > 0)
			{
				//throw new Exception("Already exists");
				return X[0];
			}
			else
			{
				for (int i = 0; i < 3; i++)
					if (!Points.Contains(pts[i]))
						Points.Add(pts[i]);
				DelaunayTriangle Res = new DelaunayTriangle(pts[0], pts[1], pts[2]);
				Triangles.Add(Res);
				return Res;
			}
		}

		DelaunayTriangle FindTriangle(params DelaunayPoint[] pts)
		{
			List<DelaunayTriangle> res = Triangles.FindAll(x => Array.Exists(pts, y => y == x.P1) && Array.Exists(pts, y => y == x.P2) && Array.Exists(pts, y => y == x.P3));
			if (res.Count == 0)
				return null;
			if (res.Count > 1)
				throw new Exception("Duplication found!");
			return res[0];
		}
		public void RemoveTriangle(DelaunayTriangle T)
		{
			foreach (DelaunayTriangle A in T.Adjacents)
				A.Adjacents.Remove(T);
			
			T.P1.MemberOf.Remove(T);
			T.P2.MemberOf.Remove(T);
			T.P3.MemberOf.Remove(T);

			if (!T.P1.MemberOf.Exists(x => T.P2.MemberOf.Contains(x)))
			{
				T.P1.Adjacents.Remove(T.P2);
				T.P2.Adjacents.Remove(T.P1);
			}
			if (!T.P2.MemberOf.Exists(x => T.P3.MemberOf.Contains(x)))
			{
				T.P2.Adjacents.Remove(T.P3);
				T.P3.Adjacents.Remove(T.P2);
			}
			if (!T.P1.MemberOf.Exists(x => T.P3.MemberOf.Contains(x)))
			{
				T.P1.Adjacents.Remove(T.P3);
				T.P3.Adjacents.Remove(T.P1);
			}

			if (T.P1.MemberOf.Count == 0)
				RemovePoint(T.P1);
			if (T.P2.MemberOf.Count == 0)
				RemovePoint(T.P2);
			if (T.P3.MemberOf.Count == 0)
				RemovePoint(T.P3);
			Triangles.Remove(T);
		}
		public void RemoveTriangle(params DelaunayPoint[] pts)
		{
			DelaunayTriangle T = FindTriangle(pts);
			if (T != null)
				RemoveTriangle(T);
		}
		public void RemovePoint(DelaunayPoint P)
		{
			for (int i = 0; i < Triangles.Count; )
			{
				if (P.MemberOf.Contains(Triangles[i]))
					RemoveTriangle(Triangles[i]);
				else
					i++;
			}
			P.MemberOf.Clear();
			foreach (var p in P.Adjacents)
				p.Adjacents.Remove(P);
			P.Adjacents.Clear();
			Points.Remove(P);
		}

		public void Generate(int N)
		{
		}

		void ByEdges(out DelaunayTriangle t1, out DelaunayTriangle t2, params DelaunayPoint[] pts)
		{
			t1 = t2 = null;
			if (pts.Length != 2)
				return;
			var Res = Triangles.FindAll(x => Array.FindAll(pts, y => y == x.P1 || y == x.P2 || y == x.P3).Length == 2);
			if (Res.Count != 2)
				return;
			t1 = Res[0];
			t2 = Res[1];
		}
		public DelaunayPoint InsertPoint(V3D p)
		{
			DelaunayPoint P = AddPoint(p);
			DelaunayTriangle Container = null;
			foreach (var T in Triangles)
				if (T.Contains(P))
					Container = T;
			if (Container != null)
			{
				RemoveTriangle(Container);
				DelaunayTriangle new1 = CreateTriangle(Container.P1, Container.P2, P);
				DelaunayTriangle new2 = CreateTriangle(Container.P2, Container.P3, P);
				DelaunayTriangle new3 = CreateTriangle(Container.P3, Container.P1, P);
				ToCheck.Clear();
				ToCheck.Add(new1);
				ToCheck.Add(new2);
				ToCheck.Add(new3);

				Check();
			}
			return P;
		}

		public static void AnalyzeCommonPoints(DelaunayTriangle T1, DelaunayTriangle T2, out DelaunayPoint A, out DelaunayPoint C1, out DelaunayPoint C2, out DelaunayPoint B)
		{
			if (T1.P1 != T2.P1 && T1.P1 != T2.P2 && T1.P1 != T2.P3)
			{
				A = T1.P1;
				C1 = T1.P2;
				C2 = T1.P3;
			}
			else if (T1.P2 != T2.P1 && T1.P2 != T2.P2 && T1.P2 != T2.P3)
			{
				A = T1.P2;
				C1 = T1.P1;
				C2 = T1.P3;
			}
			else
			{
				A = T1.P3;
				C1 = T1.P1;
				C2 = T1.P2;
			}
			if (T2.P1 != C1 && T2.P1 != C2)
				B = T2.P1;
			else if (T2.P2 != C1 && T2.P2 != C2)
				B = T2.P2;
			else
				B = T2.P3;
		}

		public List<DelaunayTriangle> ToCheck = new List<DelaunayTriangle>();
		public void CheckAll()
		{
			ToCheck.Clear();
			foreach (var T in Triangles)
				ToCheck.Add(T);
			Check();
		}

		void Check()
		{
			while (ToCheck.Count != 0)
			{
				var X = ToCheck[0];
				ToCheck.RemoveAt(0);

				if (Triangles.Contains(X))
				{
					DelaunayTriangle[] A = X.Adjacents.ToArray();

					for (int i = 0; i < A.Length; i++)
					{
						DelaunayTriangle res1, res2;
						if (CheckAndFlip(X, A[i], out res1, out res2))
						{
							ToCheck.RemoveAll(x => x == X);
							ToCheck.RemoveAll(x => x == A[i]);
							ToCheck.Add(res1);
							ToCheck.Add(res2);
							i = A.Length;
						}
					}
				}
			}
		}
		public bool CheckAndFlip(DelaunayTriangle T1, DelaunayTriangle T2,out DelaunayTriangle res1,out DelaunayTriangle res2)
		{
			if (T1.Adjacents.Contains(T2) && T2.Adjacents.Contains(T1))
			{
				DelaunayPoint A, C1, C2, B;
				AnalyzeCommonPoints(T1, T2, out A, out C1, out C2, out B);

				/*
				DelaunayTriangle t1 = FindTriangle(A, C1, C2);
				if (t1 != T1)
					throw new Exception("X");
				DelaunayTriangle t2 = FindTriangle(B, C1, C2);
				if (t2 != T2)
					throw new Exception("X");
				*/

				bool InsideCircle1 = (B.Point - T1.CCenter).Length < T1.CRadius;
				bool InsideCircle2 = (A.Point - T2.CCenter).Length < T2.CRadius;
				//if (InsideCircle1 ^ InsideCircle2)
				//	throw new AlgebraicException();
				if (InsideCircle1 && InsideCircle2)
				{
					RemoveTriangle(T1);
					RemoveTriangle(T2);
					res1 = CreateTriangle(A, C1, B);
					res2 = CreateTriangle(A, C2, B);
					//res1.Adjacents.Add(res2);
					//res2.Adjacents.Add(res1);
					return true;
				}
				res1 = T1;
				res2 = T2;
				return false;
			}
			else
				throw new Exception("Triangle adjacency integrity error");
		}
		public void Flip(DelaunayTriangle T1, DelaunayTriangle T2)
		{
			if (T1.Adjacents.Contains(T2) && T2.Adjacents.Contains(T1))
			{
				DelaunayPoint A, C1, C2, B;
				AnalyzeCommonPoints(T1, T2, out A, out C1, out C2, out B);

				DelaunayTriangle t1 = FindTriangle(A, C1, C2);
				if (t1 != T1)
					throw new Exception("X");
				DelaunayTriangle t2 = FindTriangle(B, C1, C2);
				if (t2 != T2)
					throw new Exception("X");

				RemoveTriangle(T1);
				RemoveTriangle(T2);
				CreateTriangle(A, C1, B);
				CreateTriangle(A, C2, B);
			}
			else
				throw new Exception("Triangle adjacency integrity error");
		}
		public void Write()
		{
			Console.WriteLine(Points.Count);
			int N = 0;
			foreach (var P in Points)
			{
				Console.WriteLine(N + ": " + P.Point + " | P:" + P.Adjacents.Count + " | T:" + P.MemberOf.Count);
				foreach (var A in P.Adjacents)
					Console.Write(Points.IndexOf(A) + " ");
				Console.WriteLine();
				N++;
			}
			Console.WriteLine(Triangles.Count);
			N = 0;
			foreach (var T in Triangles)
			{
				Console.WriteLine(N + ": " + T.Adjacents.Count);
				N++;
			}
		}
	}
	public class DelaunayPoint
	{
		public V3D Point;
		public List<DelaunayTriangle> MemberOf = new List<DelaunayTriangle>();
		public List<DelaunayPoint> Adjacents = new List<DelaunayPoint>();
		public DelaunayPoint(V3D P)
		{
			Point = P;
		}

		public static V3D operator -(DelaunayPoint P1, DelaunayPoint P2)
		{
			return P1.Point - P2.Point;
		}
	}
	public class DelaunayTriangle
	{
		public DelaunayPoint P1, P2;
		public DelaunayPoint P3
		{
			get
			{
				return _p3;
			}
			set
			{
				_p3 = value;
				if ((value.Point - P1.Point).Length == 0)
					throw new Exception();
			}
		}
		DelaunayPoint _p3;
		public V3D CCenter;
		public double CRadius;
		public List<DelaunayTriangle> Adjacents = new List<DelaunayTriangle>();
		public void CalcCircle()
		{
			CCenter = V3D.CircleCenter(P1.Point, P2.Point, P3.Point);
			CRadius = (CCenter - P1.Point).Length;
		}
		public DelaunayTriangle(params DelaunayPoint[] pts)
		{
			if (pts.Length != 3)
				throw new Exception("Three points needed exactly");
			if (((pts[1] - pts[0]) % (pts[2] - pts[0])).Z < 0)
			{
				DelaunayPoint temp = pts[2];
				pts[2] = pts[1];
				pts[1] = temp;
			}
			P1 = pts[0];
			P2 = pts[1];
			P3 = pts[2];

			if (!P1.Adjacents.Contains(P2))
			{
				P1.Adjacents.Add(P2);
				P2.Adjacents.Add(P1);
			}
			if (!P2.Adjacents.Contains(P3))
			{
				P2.Adjacents.Add(P3);
				P3.Adjacents.Add(P2);
			}
			if (!P1.Adjacents.Contains(P3))
			{
				P1.Adjacents.Add(P3);
				P3.Adjacents.Add(P1);
			}
			CalcCircle();
			for (int i = 0; i < 3; i++)
			{
				DelaunayTriangle commona = pts[i].MemberOf.Find(x => pts[(i + 1) % 3].MemberOf.Contains(x));
				if (commona != null)
				{
					if (commona == this)
						throw new Exception();
					commona.Adjacents.Add(this);
					Adjacents.Add(commona);
				}
			}
			for (int i = 0; i < 3; i++)
				pts[i].MemberOf.Add(this);
		}

		public bool Contains(DelaunayPoint P)
		{
			return ((P2 - P1).Unit.RotZ(90) * (P - P1).Unit) > 0
				&& ((P3 - P2).Unit.RotZ(90) * (P - P2).Unit) > 0
				&& ((P1 - P3).Unit.RotZ(90) * (P - P3).Unit) > 0;
		}
		public bool CircleContains(DelaunayPoint P)
		{
			return (P.Point - CCenter).Length < CRadius;
		}
	}
}